Матч 449, Нечетные делители (OddDivisors)

Дивизион 2, Уровень 2

Пусть f(n) - наибольший нечетный делитель натурального числа n. По заданному натуральному n необходимо вычислить значение суммы f(1) + f(2) + ... + f(n).

Класс: OddDivisors

Метод: long findSum(int n)

Ограничения: 1 £ n £ 1000000000.

Вход. Натуральное число n.

Выход. Значение суммы f(1) + f(2) + ... + f(n).

Пример входа

n

7

1

777

Пример выхода

21

1

201537

РЕШЕНИЕ

рекурсия

Если число n нечетное, то f(n) = n. Если число n четное, то f(n) = f(n / 2).

Пусть g(n) = f(1) + f(2) + ... + f(n).

Рзазобъем множество натуральных чисел от 1 до n на два подмножества: нечетных ODD = {1, 3, 5, …, 2k – 1} и четных EVEN = {2, 4, 6, …, 2l} чисел. Предполагаем, что среди натуральных чисел от 1 до n имеется в точности k = нечетных и l = четных чисел.

Тогда f(1) + f(3) + f(5) + ... + f(2k – 1) = 1 + 3 + 5 + … + (2k – 1) = = k².

В то же время f(2) + f(4) + f(6) + ... + f(2l) = f(1) + f(2) + f(3) + ... + f(l) = g(l) = .

Таким образом g(n) = k² + . Для окончания рекурсии положим g(0) = 0.

ПРОГРАММА

#include <stdio.h>

class OddDivisors

{

public:

long long findSum(long long n)

{

long long k = (n + 1) / 2;

if (n == 0) return 0;

return k * k + findSum(n / 2);

}

};